package com.leetcode.August;

import java.util.HashMap;

/**
 * @Description: 随机链表的复制
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-01 23:22
 */
public class copyRandomLists {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 创建哈希表，键为原节点，值为新节点
        Map<Node, Node> nodeMap = new HashMap<>();

        // 第一次遍历，创建新节点并存储映射关系
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            nodeMap.put(current, newNode);
            current = current.next;
        }
        // 第二次遍历，设置新节点的 next 和 random 指针
        current = head;
        while (current != null) {
            Node newNode = nodeMap.get(current);
            newNode.next = nodeMap.get(current.next);
            newNode.random = nodeMap.get(current.random);
            current = current.next;
        }

        // 返回新链表的头节点
        return nodeMap.get(head);
    }
}
